ТЕМА: ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
ТЕМА: ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
ЗАДАЧА 2.А. Решение задачи линейного программирования
графическим методом
Вариант 10. Найти максимальное и минимальное значения
линейной функции Ф = 2·x1 — 3·x2
при ограничениях: x1 + 3·x2 ≤ 18;
2·х1
х2 ≤ 5;
3·х1 ≤ 21;
х i ≥ 0, i = 1,2.
Заменив условно знаки неравенств знаками равенств, получим систему уравнений
x1 + 3·x2 = 18 (1);
2·х1 + х2 = 16 (2);
х2 = 5 (3);
3·х1 = 21 (4).
Построим по этим уравнениям прямые, затем в соответствии со знаками неравенств выделим полуплоскости и получим их общую часть — область допустимых решений ОДР – многоугольник MNPQRS.
Построим вектор Г(2; -3) и через начало координат проведем линию уровня – прямую .
Перемещаем линию уровня в направлении , значение Ф при этом растет. В точке S(7; 0) целевая функция достигает максимума Фmax=2·7–3·0= = 14. Перемещаем линию уровня в направлении , значение Ф при этом убывает. Минимальное значение функции — в точке N(0; 5)
Фmin = 2·0 – 3·5 = –15.
Внимание!
Это ОЗНАКОМИТЕЛЬНАЯ ВЕРСИЯ работы №2072, цена оригинала 200 рублей. Оформлена в программе Microsoft Word.
Оплата. Контакты.
ЗАДАЧА 2.B. Решение задачи линейного программирования
аналитическим симплексным методом
Вариант 10. Максимизировать целевую функцию Ф = x2 + x3
|
при ограничениях: x1 — x2 + x3 = 1,
x2 — 2·х3 + х4 = 2.
Решение:
Система уравнений — ограничений совместна, так как ранги матрицы системы уравнений и расширенной матрицы одинаковы и равны 2. Следовательно, две переменные можно принять в качестве свободных, две другие переменные — базисные — выразить линейно через две свободные.
Примем за свободные переменные x2 и х3.Тогда базисными будут переменные х1 и х2, которые выразим через свободные
x1 = 1 + x2 — x3; (*)
x4 = 2 — x2 + 2·x3;
Целевая функция уже выражена через x2 и x3, то есть, Ф = x2 + x3.
При х2=0 и х3=0 базисные переменные будут равными х1 = 1, х4 = 2.
Имеем первое допустимое решение Х1 = (1, 0, 0, 2), при этом Ф1 = 0.
Увеличение Ф возможно при увеличении, например, значения х3, который входит в выражение для Ф с положительным коэффициентом (x2 при этом остается равным нулю). В первое уравнение системы (*) видно, что х3 можно увеличивать до 1 (из условия х1 ³0), то есть это уравнение накладывает ограничение на увеличение значения х3. Первое уравнение системы (*) является разрешающим. На базе этого уравнения переходим к новому базису, поменяв х1 и х3 местами. Теперь базисными переменными будут х3 и x4, свободными — x1 и x2. Выразим теперь х3 и x4 через х1 и х2.
Получим: x3 = 1 — x1 + x2; (**)
x4 = 4 — 2·x1 + x2;
Ф = х2 + 1 — х1 + х2 = 1 — x1 + 2·x2
Приравняв нулю свободные переменные, получим второе допустимое базисное решение Х2= (0; 0; 1; 4), при котором Ф2=1.
Увеличение Ф возможно при увеличении х2. Увеличение же х2, судя по последней системе уравнений (**), не ограничено. Следовательно, Ф будет принимать все большие положительные значения, то есть, Фмах = + ¥.
Итак, целевая функция Ф не ограничена сверху, потому оптимального решения не существует.
ЗАДАЧА 2.D. Составить задачу, двойственную к приведенной
исходной задаче.
Вариант 10. Минимизировать функцию Ф = х1 + х2 + х3
при ограничениях: 3×х1 + 9×х2 + 7×х3 ≥ 2,
6×х1 + 4·х2 + 5×х3 ≥ 3,
8×х1 + 2·х2 + 4×х3 ≥ 4,
Решение:
Имеем исходную задачу на минимизацию с системой ограничений в виде неравенств, то есть, пара двойственных задач имеет симметричный вид 3-го типа, математическая модель которых в матричной форме имеет вид:
Исходная задача Двойственная задача
Ф = С× Х min F = BТ×Y max
при А × Х ≥ В при AТ ×Y ≤ СТ
Х ≥ 0 Y ≥ 0
В исходной задаче матрица-строка коэффициентов при переменных в целевой функции, матрица-столбец свободных членов и матрица коэффициентов при переменных в системе ограничений имеют вид
2 3 9 7
С = (1; 1; 1), В = 3 , А = 6 4 5
4 8 2 4
Найдем матрицы двойственной задачи
2 3 6 8
ВT = (2; 3; 4) СT = 3 AT = 9 4 2
4 7 5 4
Двойственная задача формулируется в виде:
Максимизировать целевую функцию F = 2y1 + 3y2 + 4y3
при ограничениях 3×y1 + 6×y2 + 8×y3 ≤ 1,
9×y1 + 4×y2 + 2×y3 ≤ 1,
7×y1 + 5×y2 + 4×y3 ≤ 1,
yi ≥ 0 (i = 1, 2, 3)
ЗАДАЧА 2.С. Решение задачи линейного программирования с помощью симплексных таблиц.
********************
Вариант 10. Минимизировать целевую функцию Ф = x1 + x2,
|
при ограничениях: x1 –2·x3 + x4 = 2,
x2 – x3 + 2·x4 = 1,
Решение:
Количество переменных равно 5, ранг матрицы — 3, следовательно количество свободных переменных равно r = 6-3 = 2. В качестве свободных переменных примем х3 и х4, в качестве базисных — x1, x2, x5. Все уравнения системы уже приведены к единичному базису (базисные переменные выражены через свободные), но записаны в виде, не удобном к применению симплекс-таблиц. Запишем систему уравнений в виде
x1 — 2·x3 + x4 = 2
x2 — x3 +2·x4 = 1
x5 + x3 — x4. = 5
Целевую функцию выразим через свободные переменные и запишем в виде Ф — 3·x3 +3·x4 = 3
Составим таблицу
I итерация Таблица 1
| Базисн. перем. | Свобод. перем. | х1 | х2 | х3 | х4 | х5 | bi/aip | aip/aqp |
| х1 | 2 | 1 | 0 | -2 | 1 | 0 | 2 | -1/2 |
| х2 | 1 | 0 | 1 | -1 | 0 | 1/2 | 1/2 | |
| х5 | 5 | 0 | 0 | 1 | -1 | 1 | 1/2 | |
| Ф | 3 | 0 | 0 | -3 | 3 | 0 | -3/2 |
Х1 = (2; 3; 0; 0; 5) Ф1 = 3.
Таблица 2
| х1 | 3/2 | 1 | -1/2 | -3/2 | 0 | 0 | ||
| х4 | 1/2 | 0 | 1/2 | -1/2 | 1 | 0 | ||
| х5 | 11/2 | 0 | 1/2 | 1/2 | 0 | 1 | ||
| Ф | 3/2 | 0 | -3/2 | -3/2 | 0 | 0 |
Х2 = (3/2; 0; 0; 1/2; 11/2) Ф2 = 3/2.
В индексной строке последней таблицы нет положительных чисел, то есть, в выражении для целевой функции все Гi > 0. Имеем случай 1, следовательно, последнее базисное решение является оптимальным.
Ответ : Фmin= 3/2, оптимальное решение (3/2; 0; 0; 1/2; 11/2).